package string;

/**
 * 给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
 * 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
 * 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
 * 请你返回纸上能写出的字典序最小的字符串。
 * <p>
 * 示例 1：
 * 输入：s = "zza"
 * 输出："azz"
 * 解释：用 p 表示写出来的字符串。
 * 一开始，p="" ，s="zza" ，t="" 。
 * 执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
 * 执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
 * <p>
 * 示例 2：
 * 输入：s = "bac"
 * 输出："abc"
 * 解释：用 p 表示写出来的字符串。
 * 执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
 * 执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
 * 执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
 * 执行第二个操作，得到 p="abc" ，s="" ，t="" 。
 * <p>
 * 示例 3：
 * 输入：s = "bdda"
 * 输出："addb"
 * 解释：用 p 表示写出来的字符串。
 * 一开始，p="" ，s="bdda" ，t="" 。
 * 执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
 * 执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。
 *
 * @author Jisheng Huang
 * @version 20250606
 */
public class RobotWithString_2434 {
    /**
     * 根据题意，t 中字符是先进后出的，是一个栈。
     * <p>
     * 问题相当于从左到右遍历 s，在允许用一个辅助栈的前提下，计算能得到的字典序最小的字符串。
     * <p>
     * 看示例 2，s=bac：
     * <p>
     * s[0]=b 入栈，能立刻出栈吗？
     * 如果立刻出栈，那么答案的第一个字母是 b。
     * 如果不出栈，后面遍历到 a 的时候把 a 出栈，那么答案的第一个字母就会是 a，字典序更小。
     * 因此，如果我们发现后面有更小的字母，那就不出栈。
     * s[1]=a 入栈，能立刻出栈吗？
     * 如果立刻出栈，那么答案的第一个字母是 a。
     * 如果不出栈，后面也没有更小的字母了。把 c 入栈再出栈，答案的第一个字母是 c，不是最优的。
     * 因此，如果我们发现当前字母比剩余字母（后缀 s[i+1:]）中的最小值还小，那么就立刻出栈。
     * 此外，a 出栈后，应该继续把栈顶的 b 也出栈，不然后面 c 入栈出栈，会把 c 填到答案的第二个位置上，不是最优的。
     * s[2]=c 入栈，再出栈。
     * 最终答案为 abc。
     * 如果 s 中有相同字母，要如何处理呢？
     * <p>
     * 以 s=caba 为例。对于 s[1]=a，应该立刻出栈。如果不出栈，遍历到 s[3]=a 才出栈，那么结果是 abac，但正确答案是 aabc。在错误答案中，因为没有及时把 a 出栈，我们把更大的 b 插在了两个 a 中间。所以如果栈顶等于剩余字母（后缀 s[i+1:]）中的最小值，也应该立刻出栈。
     * <p>
     * 总结：如果栈顶 ≤ 剩余字母（后缀 s[i+1:]）中的最小值，就立刻出栈。
     *
     * @param s the given string
     * @return
     */
    public static String robotWithString(String s) {
        char[] arr = s.toCharArray();
        int n = s.length();
        char[] sufMin = new char[n + 1];
        sufMin[n] = Character.MAX_VALUE;

        for (int i = n - 1; i >= 0; --i) {
            sufMin[i] = (char) Math.min(sufMin[i + 1], arr[i]);
        }

        char[] ans = arr;
        char[] st = sufMin;
        int idx = 0;
        int top = -1;

        for (int i = 0; i < n; ++i) {
            st[++top] = arr[i];

            while (top >= 0 && st[top] <= sufMin[i + 1]) {
                ans[idx++] = st[top--];
            }
        }

        return new String(ans);
    }

    public static void main(String[] args) {
        System.out.println(robotWithString("zza"));
        System.out.println(robotWithString("bac"));
        System.out.println(robotWithString("bdda"));
    }
}
